package developer.算法.链表.排序链表;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangyongkang
 * @time 2025/3/20 19:58
 * @description 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 * <p>
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 */
public class PaiXuLianBiao {
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    /**
     * 两种思路
     * 1. 进行选择排序
     * 2. 放到一个sortSet后进行重新构建
     *
     * @param head
     * @return
     */


    public static void main(String[] args) {
        ListNode listNode = sortList(new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3)))));
        if (listNode != null) {
            while (listNode != null) {
                System.out.println(listNode.val);
                listNode = listNode.next;
            }
        }

    }


    public static ListNode sortList(ListNode head) {
        List<ListNode> sortList = new ArrayList<>();
        while (head != null) {
            sortList.add(head);
            head = head.next;
        }
        sortList.sort((a, b) -> a.val - b.val);
        ListNode result = new ListNode();
        ListNode current = result;
        for (ListNode listNode : sortList) {
            current.next = listNode;
            listNode.next = null;
            current = listNode;
        }
        return result.next;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
